package com.hdu.hot100.list;

import java.util.Comparator;
import java.util.List;
import java.util.Objects;
import java.util.PriorityQueue;

public class lc23 {


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            PriorityQueue<ListNode> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.val));
            for (ListNode headNode : lists) {
                if (Objects.nonNull(headNode))
                    pq.add(headNode);
            }
            ListNode dummy = new ListNode(-1);
            ListNode cur = dummy;
            while (!pq.isEmpty()) {
                ListNode node = pq.poll();
                cur.next = node;
                cur = cur.next;
                if (Objects.nonNull(node.next))
                    pq.add(node.next);
            }
            return dummy.next;
        }

    }
}
